The Routing of Complex Contagion in Kleinberg's Small-World Networks

摘要

In Kleinberg's small-world network model, strong ties are modeled asdeterministic edges in the underlying base grid and weak ties are modeled asrandom edges connecting remote nodes. The probability of connecting a node $u$with node $v$ through a weak tie is proportional to $1/|uv|^\alpha$, where$|uv|$ is the grid distance between $u$ and $v$ and $\alpha\ge 0$ is theparameter of the model. Complex contagion refers to the propagation mechanismin a network where each node is activated only after $k \ge 2$ neighbors of thenode are activated. In this paper, we propose the concept of routing of complex contagion (orcomplex routing), where we can activate one node at one time step with the goalof activating the targeted node in the end. We consider decentralized routingscheme where only the weak ties from the activated nodes are revealed. We studythe routing time of complex contagion and compare the result with simplerouting and complex diffusion (the diffusion of complex contagion, where allnodes that could be activated are activated immediately in the same step withthe goal of activating all nodes in the end). We show that for decentralized complex routing, the routing time is lowerbounded by a polynomial in $n$ (the number of nodes in the network) for allrange of $\alpha$ both in expectation and with high probability (in particular,$\Omega(n^{\frac{1}{\alpha+2}})$ for $\alpha \le 2$ and$\Omega(n^{\frac{\alpha}{2(\alpha+2)}})$ for $\alpha > 2$ in expectation),while the routing time of simple contagion has polylogarithmic upper bound when$\alpha = 2$. Our results indicate that complex routing is harder than complexdiffusion and the routing time of complex contagion differs exponentiallycompared to simple contagion at sweetspot.